package com.cty._03_SolutionSeekingMindset._27_MirrorOfBinaryTree;

import java.util.Stack;

/**
 * @Auther: cty
 * @Date: 2020/7/10 10:10
 * @Description: 面试题27：二叉树的镜像
 * 题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。
 * @version: 1.0
 */
public class MirrorOfBinaryTree {

    /**
     * 递归实现
     */
    public static BinaryTreeNode mirror(BinaryTreeNode treeRoot){
        if(treeRoot == null)
            return null;

        mirrorRecursively(treeRoot);
        return treeRoot;
    }


    private static void mirrorRecursively(BinaryTreeNode treeRoot){

        if(treeRoot.leftChild==null && treeRoot.rightChild==null)
            return;

        BinaryTreeNode temp = treeRoot.leftChild;
        treeRoot.leftChild = treeRoot.rightChild;
        treeRoot.rightChild = temp;

        if(treeRoot.leftChild != null)
            mirrorRecursively(treeRoot.leftChild);
        if(treeRoot.rightChild != null)
            mirrorRecursively(treeRoot.rightChild);
    }  // end mirrorRecursively

    /**
     * 堆栈实现
     */
    public static BinaryTreeNode mirrorIteratively(BinaryTreeNode treeRoot){
        if(treeRoot == null)
            return null;

        Stack<BinaryTreeNode> stack = new Stack<>();
        stack.push(treeRoot);

        while(!stack.isEmpty()){
            BinaryTreeNode node = stack.pop();

            if(node.leftChild==null && node.rightChild==null)
                continue;

            BinaryTreeNode temp = node.leftChild;
            node.leftChild = node.rightChild;
            node.rightChild = temp;

            if(node.leftChild != null)
                stack.push(node.leftChild);
            if(node.rightChild != null)
                stack.push(node.rightChild);
        }  // end while()
        return treeRoot;
    }  // end mirrorIteratively()

}  // end class

class BinaryTreeNode {
    int value;
    BinaryTreeNode leftChild;
    BinaryTreeNode rightChild;

    public BinaryTreeNode(){}

    public BinaryTreeNode(int value){
        this.value = value;
    }
}  // end class
